import java.util.*;

public class Test_9_16 {

    //力扣：771. 宝石与石头
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set = new HashSet<>();
        for(int i = 0; i < jewels.length(); i++) {
            set.add(jewels.charAt(i));
        }

        int ret = 0;
        for(int i = 0; i < stones.length(); i++) {
            if(set.contains(stones.charAt(i))) {
                ret++;
            }
        }
        return ret;
    }


    //牛客网：[编程题]旧键盘 (20)
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String input = in.nextLine();
            String output = in.nextLine();
            input = input.toUpperCase();
            output = output.toUpperCase();
            HashSet<Character> set = new HashSet<>();
            for(int i = 0; i < output.length(); i++) {
                set.add(output.charAt(i));
            }
            for(int i = 0; i < input.length(); i++) {
                char ch = input.charAt(i);
                if(!set.contains(ch)) {
                    System.out.print(ch);
                    set.add(ch);
                }
            }
        }
    }





    //692. 前K个高频单词
    class cmp implements Comparator<Map.Entry<String, Integer>> {
        @Override
        public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
            if(o1.getValue() == o2.getValue()) {
                //按照字母顺序建立大根堆
                return o2.getKey().compareTo(o1.getKey());
            }

            return o1.getValue() - o2.getValue();
        }
    }
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();
        // 1. 得到每个单词出现的次数
        for (String word: words) {
            if(map.get(word) == null) {
                map.put(word, 1);
            } else {
                int val = map.get(word);
                map.put(word, val + 1);
            }
        }

        // 2. 创建一个以 value 值比较的小根堆
        PriorityQueue<Map.Entry<String, Integer>> minheap = new PriorityQueue<>(new cmp());

        for (Map.Entry<String, Integer> entery : map.entrySet()) {
            // 当前堆的元素个数小于 k 时，先入队
            if(minheap.size() < k) {
                minheap.offer(entery);
            } else {
                Map.Entry<String, Integer> top = minheap.peek();
                //当前单词出现的频率 与 堆顶 单词出现频率相同时， 单词在字典中的顺序小的入堆
                if(entery.getValue().equals(top.getValue())) {
                    if(entery.getKey().compareTo(top.getKey()) < 0) {
                        minheap.poll();
                        minheap.offer(entery);
                    }
                    //当前单词出现频率 ＞ 堆顶单词出现频率时， 当前单词入堆
                } else if(entery.getValue().compareTo(top.getValue()) > 0) {
                    minheap.poll();
                    minheap.offer(entery);
                }
            }
        }

        // 3. 把小根堆元素出队放入数组
        List<String> list = new ArrayList<>();
        for (int i = 0; i < k ; i++) {
            Map.Entry<String, Integer> top = minheap.poll();
            list.add(top.getKey());
        }
        //翻转数组
        Collections.reverse(list);
        return list;
    }
}
